#include "types.h"
#include "defs.h"
#include "param.h"
#include "mmu.h"
#include "x86.h"
#include "proc.h"
#include "spinlock.h"
#include "sched_stride.h"
#include "rq.h"
//#define QUEUE_DEBUG
//#define TICKET_DEBUG
//#define PASS_DEBUG
// by fw:
#define RESPONSE_DEBUG

void printrq(struct rq* rq)
{
	struct rq_node* node = rq->head;
	while(node != NULL){
		cprintf("[pid=%d, pass=%d] ", node->proc->pid, node->proc->pass);
		node = node->next;
	}
	cprintf("\n");
}
struct rq_node* find_rq_node(struct rq* rq, struct proc* p)
{
	struct rq_node* node_find = rq->head;

	while(node_find != NULL && node_find->proc != p){
	   node_find = node_find->next;
	}

	if(node_find == NULL){
	   panic("node not found");
	   return NULL;
	}else{
	   return node_find;
	}
}

void queue_delete(struct rq* rq, struct proc* p)
{
	struct rq_node* node_find = NULL;

	node_find = find_rq_node(rq, p);
	if(node_find == rq->head){
		//when only 1 proc in queue
		if(node_find->next == NULL){
		   //rq->head = node_find->prev = node_find ->next = NULL;
           rq->head = NULL;
		}else{
        //when 2 or more procs in queue
           rq->head = rq->head->next;
		   rq->head->prev = NULL;
		   node_find->next = NULL;
		   //rq->head->prev = NULL;
		   //node_find>next = NULL;
		}		
	}else if(node_find->next == NULL){
       //when p at the tail of the queue
       node_find->prev->next = NULL;
	   node_find->prev = NULL;
	}else{
	   //when p in the middle of the queue
       node_find->prev->next = node_find->next;
	   node_find->next->prev = node_find->prev;
	   node_find->next = node_find->prev =NULL;
	}	
	node_find->proc =NULL;
	if(rq->free_list!=NULL){
       rq->free_list->prev = node_find;
	   node_find->next = rq->free_list;
	}
	rq->free_list = node_find;
}


void queue_insert(struct rq* rq, struct proc* p)
{
	struct rq_node* new_node = rq->free_list;

	//struct rq_node* head = rq->head;
	rq->free_list = rq->free_list->next;
	if(rq->free_list!=NULL)
	{
	    rq->free_list->prev = NULL;
	}
	new_node->next = new_node->prev = NULL;
	new_node->proc = p;
	p->rq = rq;

	if(rq->head == NULL){
		//when rq is empty
	   rq->head = new_node;
	}else if(p->pass <= rq->head->proc->pass){
       //when p->pass <= head->pass
	   rq->head->prev = new_node;
       new_node->next = rq->head;
	   rq->head = new_node;	   
	}else{
	   //when p->pass > head->pass
	   struct rq_node* tmp_node = rq->head;
	   while(tmp_node->proc->pass < p->pass && tmp_node->next != NULL){
	      tmp_node = tmp_node->next;
	   }
	   if(tmp_node->next != NULL){
		  //when p should be insert into the middle of the queue
	      tmp_node->prev->next = new_node;
		  new_node->prev = tmp_node->prev;
		  new_node->next = tmp_node;
		  tmp_node->prev = new_node;
	   }else{
		   if(tmp_node->proc->pass <= p->pass){
			   //when p should be insert after the tail
		      tmp_node->next = new_node;
			  new_node->prev = tmp_node;
		   }else{
			   //when p should be insert before the tail
              tmp_node->prev->next = new_node;
			  new_node->prev = tmp_node->prev;
			  new_node->next = tmp_node;
			  tmp_node->prev = new_node;			  
		   }
	   }	   
	}
}

void queue_flesh(struct rq* rq, struct proc* p)
{
	//struct rq_node* node_find = find_rq_node(rq, p);
	queue_delete(rq, p);
	queue_insert(rq, p);
}

void global_ticket_update(struct rq* rq, int ticket_delta)
{
#ifdef TICKET_DEBUG
    cprintf("before global_ticket_update:  rq->global_ticket = %d ,  rq->global_pass = %d\n", rq->global_ticket,rq->global_pass);
#endif
	rq->global_ticket += ticket_delta;
	//should be careful when ticket becomes ZERO
	//***need more consideration!!!***
	if( rq->global_ticket != 0){
	   rq->global_stride = sched_class_stride.stride1 / rq->global_ticket;
	}
#ifdef TICKET_DEBUG
	cprintf("after global_ticket_update:  rq->global_ticket = %d ,  rq->global_pass = %d\n", rq->global_ticket,rq->global_pass);
#endif
}

void global_pass_update(struct rq* rq)
{
	//***here should acquire ticks_lock first***
	//***need more consideration!!!***
	static int last_update = 0;
	int elapsed;
#ifdef PASS_DEBUG
	cprintf("before global_pass_update:  rq->global_ticket = %d ,  rq->global_pass = %d\n", rq->global_ticket,rq->global_pass);
#endif
	acquire(&tickslock);
	elapsed =  ticks - last_update;
	last_update = ticks;
	release(&tickslock);
	if(rq->global_ticket != 0){
	   rq->global_pass += rq->global_stride * elapsed / sched_class_stride.timeslice;
	}
#ifdef PASS_DEBUG
	cprintf("after global_pass_update:  rq->global_ticket = %d ,  rq->global_pass = %d\n", rq->global_ticket,rq->global_pass);
#endif
	
}
void init_rq_stride(struct rq* rq){
  int i;

  rq->head = NULL;

  //init first element and free_list head
  rq->nodes[0].proc = NULL;
  rq->nodes[0].prev = NULL;
  rq->nodes[0].next = &(rq->nodes[1]);
  rq->free_list = &(rq->nodes[0]);

  //mark nodes from 1 to NPROC -1 free and linked
  for(i = 1; i < NPROC - 1; i++){
    rq->nodes[i].proc = NULL;
	rq->nodes[i].prev = &(rq->nodes[i-1]);
	rq->nodes[i].next = &(rq->nodes[i+1]);
  }

  //mark last node free and linked
  rq->nodes[i].prev = &(rq->nodes[i-1]);
  rq->nodes[i].next = NULL;

  rq->proc_num = 0;
  rq->global_ticket = 0;
  rq->global_pass = 0;

}

void enqueue_proc_stride(struct rq* rq, struct proc *p){
  //struct rq_node* new_node = NULL;
  
  //get a new_node from free_list, connect p and new_node,update proc_num
  /*new_node = rq->free_list;
  rq->free_list = rq->free_list->next;
  free_list->prev = NULL;
  new_node->next = NULL;
  new_node->proc = p;*/
  //p->rq = rq;
  (rq->proc_num)++;
#ifdef QUEUE_DEBUG
  cprintf("pid=%d has enqueued,  now rq has %d procs\n",p->pid, rq->proc_num);
#endif
  

  //update pass and ticket
  global_pass_update(rq);
  p->pass = p->remain + rq->global_pass;
#ifdef TICKET_DEBUG
  //cprintf("p->pass = %d   p->remain= %d    rq->global_pass= %d\n", p->pass,p->remain,rq->global_pass);
#endif
  global_ticket_update(rq, p->ticket);

  //insert p into rq in ascending order of pass value
  queue_insert(rq, p);
#ifdef QUEUE_DEBUG
  printrq(rq);
#endif
}

//pay attention this func doesn't change p's state and p's state mustn't be running
void dequeue_proc_stride(struct rq *rq, struct proc *p){

  global_pass_update(rq);
  p->remain = p->pass - rq->global_pass;
#ifdef PASS_DEBUG
  cprintf("p->pass = %d   p->remain= %d    rq->global_pass= %d\n", p->pass,p->remain,rq->global_pass);
#endif
  global_ticket_update(rq, -(p->ticket));
  queue_delete(rq, p);
  (rq->proc_num)--;
#ifdef QUEUE_DEBUG
  cprintf("pid=%d has dequeued,  now rq has %d procs\n",p->pid, rq->proc_num);
  printrq(rq);
#endif
}

//when idle yields, do nothing. return to yield() to handle;
//when normal proc yields, re_insert into the rq
//***However this can cause this very proc be picked again!!! instead of chose another***
//proc's state doesn't change
void yield_proc_stride(struct rq *rq){
	struct proc* p = cp; //pay attention to cp ,this maybe dangerous when current proc changes! esp when interrupt is on

	//here use debug information, not a good way.
	if(p == idleproc[cpu()]){
#ifdef IDLE_DEBUG
	   cprintf("proc idle yield\n");
#endif
	   return;
	}
	else{       
	   p->pass += p->stride * (p->timeslice - p->timeleft) / p->timeslice;
	}
#ifdef YIELD_DEBUG
	//if(cp->pid > 2)
	cprintf("proc pid=%d yield with timeleft=%d\n", p->pid, p->timeleft);
#endif
	if(p->timeleft == 0)
	   p->timeleft = p->timeslice;
	queue_flesh(rq, p);
}

struct proc* pick_next_proc_stride(struct rq *rq){
  //pay attenion rq->head doesn't change when return
  if(rq->head != NULL)
     return rq->head->proc;
  else
     return NULL;
}
#ifdef RESPONSE_DEBUG
 int now;
 int response[1000] = {0};
 int last_tick = 0;
#endif

void proc_tick_stride(struct rq* rq, struct proc* p){
   if(p == idleproc[cpu()]){
       //pay attention to the state of the proc
	   yield();
   }else{
      p->timeleft--;
#ifdef TICK_DEBUG
	  //if(cp->pid > 2)
	  cprintf("proc pid=%d tick_interrupt with timeleft=%d\n", p->pid, p->timeleft);
#endif
      if(p->timeleft == 0){
#ifdef RESPONSE_DEBUG
		  if(p->pid == 10){
			  acquire(&tickslock);
			  now = ticks;
			  release(&tickslock);
			  if(last_tick == 0){
				  last_tick = now;
			  }
			  else{
				  response[now - last_tick]++;
				  last_tick = now;
			  }
		  }
#endif
          yield();
      }
   }
}

//// by jimmy:
//void load_balance_simple(struct rq* rq){
//  int max = 0;
//  struct rq* src_rq = 0;
//  int i;
//  struct proc* procs_moved[NPROC/2];
//  int num_procs_moved;
//  
//  // find out the busiest rq
//  for(i=0; i<ncpu; i++){
//    if(rqs[i].proc_num > max){
//      src_rq = &(rqs[i]);
//      max = src_rq->proc_num;
//    }
//  }
//  if(src_rq == 0)
//    return;
//
//  // Get the proc from src_rq
//  acquire(&(src_rq->rq_lock));
//  num_procs_moved = src_rq->sched_class->get_proc(src_rq, procs_moved);
//  release(&(src_rq->rq_lock));
//
//  if(num_procs_moved != 0)
//    cprintf("load_balance\n");
//
//  acquire(&(rq->rq_lock));
//  for(i=0; i<num_procs_moved; i++) {
//    enqueue_proc(rq, procs_moved[i]);
//  }
//  release(&(rq->rq_lock));
//
//  return;
//}
//
//// by jimmy:
//int get_proc_simple(struct rq* rq, struct proc* procs_moved[]){
//  int num_procs_moved;
//  int i;
//  struct rq_node* prev, *next, *cnod
//
//  num_procs_moved = rq->proc_num/2;
//
//  cnode = rq->next_to_run->next;
//  for(i=0; i<num_procs_moved; i++){
//    if(cnode->next == 0){
//      release(&(rq->rq_lock));
//      cprintf("Wrong here: proc_num = %d\n", rq->proc_num);
//      panic("Not enough proc to move in get_proc_simple\n");
//    }
//    procs_moved[i] = cnode->proc;
//    prev = cnode->prev, next = cnode->next;
//    prev->next = next;
//    next->prev = prev;
//    cnode->next = rq->free_list;
//    rq->free_list = cnode;
//    cnode = next;
//  }
//  rq->proc_num -= num_procs_moved;
//
//  return num_procs_moved;
//}

const struct sched_class sched_class_stride = {
  .init_rq		= init_rq_stride,
  .enqueue_proc		= enqueue_proc_stride,
  .dequeue_proc		= dequeue_proc_stride,
  .yield_proc		= yield_proc_stride,
  .pick_next_proc	= pick_next_proc_stride,
  .proc_tick		= proc_tick_stride,
  .stride1          = 100000000,
  .timeslice        = 5
  //.load_balance		= load_balance_simple,
  //.get_proc		= get_proc_simple,
};

